function mergeSort(arr){
    if(arr===null||arr.length<2){
        return ;
    }

    mergeSortCal(arr,0,arr.length);
    arr.shift();
    return arr;    
}


function mergeSortCal(arr,left,right){
    if(left===right){
        return ;
    }

    let mid = left + ~~((right - left)>>2);

    mergeSortCal(arr,left,mid);
    mergeSortCal(arr,mid+1,right);
    merge(arr,left,mid,right);
}


function merge(arr,left,mid,right){
    let 
        temp = [],
        p1 = left,
        p2 = mid+1;

    let i = 0;
    while(p1<=mid&&p2<=right){
        temp[i++] =  arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
    }
    while(p1<=mid){
        temp[i++] = arr[p1++];
    }
    while(p2<right){
        temp[i++] = arr[p2++];
    }
    for(let i=0;i<temp.length;i++){
        arr[left+i] = temp[i];
    }
}


let arr = [11, 561, 123, 78, 99, 20];
console.log(mergeSort(arr));